package com.lijing.coinChange;

/**
 * @Description coinChange
 * @title: CoinChange01
 * @Author LiJing
 * @Date: 2021/4/69:26 上午
 * @Version 1.0
 */
public class CoinChange01 {
    public static void main(String[] args) {
        int[] coins = {1,2,5};
        int target = 13;
        System.out.println(coinChange(coins,target));
    }

    /**
     *
     * @param coins a list of integer
     * @param target a total amount of money amount
     * @return the fewest number of coins you need to make up
     */
    public static int coinChange(int[] coins, int target){
        int coinsRange = coins.length;
        int[] fewestNum = new int[target+1];
        //initialization
        fewestNum[0] = 0;

        //1,2,3,4...,target
        for (int i = 1; i <= target; i++) {
            fewestNum[i] = Integer.MAX_VALUE;
            for (int j = 0; j < coinsRange; j++) {
                if (i >= coins[j] && fewestNum[i-coins[j]] != Integer.MAX_VALUE){
                    fewestNum[i] = Math.min(fewestNum[i-coins[j]]+1,fewestNum[i]);
                }
            }
        }
        if (fewestNum[target] == Integer.MAX_VALUE){
            return -1;
        }
        return fewestNum[target];
    }
}
